package com.fifth;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * HashMap是一种数据结构，通过key-value的形式来存储数据
 * JDK 1.8版本之前：实现 数组+链表
 * JDK 1.8版本之后：实现 数组+链表+二叉树（红黒树）
 * 默认初始容量（16），指的是内部实现的对象数组的大小，和默认加载因子（0.75）。
 * 哈希表的都大容量，整数值的一半
 * 加载因子是指哈希表（数组）的容量满了75%时，表示需要扩容（哈希表需要重新散列）
 * <p>
 * 数组+链表的含义指的是：每个数组的位置上的对象，是一个链表结构存储（换句话说，
 * 这样的方式就可以在数组的每个位置中存储多个对象）
 * <p>
 * 对象的hashCode方法，是 Object类中定义的，就是用来给哈希表使用的,本身是一个本地方法，使用
 * C/C++来实现，同一个对象多次调用hashCode方法，应该返回相同的int值（HashCode值）
 * <p>
 * return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 * h >>> 16  无符号右移16位（因为整数是32位，右移16位）
 * <p>
 * HashMap在第一次put时，才进行初始化
 * put对象的过程：
 * 求key对象的hash值，再通过哈希表数组的最大下标值&hash值（值永远<=下标值） 得出的结果，
 * 来作为哈希表数组的下标位置，这个位置就是对象存储的位置
 * 取值的原理与存储的原理一致，也是通过求hash值来确定哈希表的位置，如果此位置上有链表对象，那么需要遍历链表
 * <p>
 * HashMap 扩容的机制是什么？
 * 当容量到达75%的阀值后，进行扩容，扩容的算法是 oldCap<<1,表示*2，
 * 扩容了之后，那么需要把原哈希表中的数据，重新计算哈希值存储到新的哈希表中
 * <p>
 * 如果相同对象KEY的hashCode值不同，那么在Hash表中存储的对象就无法取出，又不会被垃圾收集器回收，
 * 此种情况称为内存泄露，内存泄露过多，就是会发生内存溢出；
 * 面试题：说 JAVA 有内存泄露吗，为什么？
 * <p>
 * 重新扩容之后，原来的对象位置不保正有序
 * <p>
 * JDK 1.8版本之后：实现 数组+链表+二叉树（红黒树）
 * 改进的原因：如果数组中同一个位置的链表过长，那么会影响查询遍历的性能（因为链表不适合遍历）
 * 改进方法是：把链表变成二叉树（数组+二叉树）
 * 怎么变？什么时候变？
 * 转化成红黑树的条件，是 KEY 值的总数大于64时
 * 在扩容时，当哈希表中数组同一个位置中的链表长度大于8时（阀值），那么会把链表转换成红黑树，来提高查询效率
 * 在扩容时，当哈希表中数组同一个位置中的红黑树长度小于6时（阀值），那么会把红黑树转换成链表
 * 在阀值6和8之间留个7的原因是为了防止链表和红黑树来回的转换，影响性能（防抖）
 * <p>
 * 红黑树是在均衡二叉树上扩展，特点：（掌握特点）
 * 1、每个节点非红即黑
 * 2、根节点总是黑色的
 * 3、如果节点是红色的，则它的子节点必须是黑色的(反之不一定)
 * 4、每个叶子节点都是黑色的空节点(NIL 节点)
 * 5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点(即相同的黑色高度)
 * <p>
 * HashMap缺点：
 * 1、线程不安全
 * 2、避免哈希表频繁散列（rehash），重新rehash会消耗性能
 * new HashMap(initialCapacity); 通过设置合理的初始容量
 * <p>
 * 优点：取值快，优其在数据量越大表现越明显
 * HashMap 的结构通过会被用来设计缓存、框架底层的数据结构
 */
public class HashMapDemo {
    public static void main(String[] args) {
        // HashMap遍历
        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(1, "Jim");
        map.put(2, "Json");
        map.put(3, "Jack");

        Set<Integer> integers = map.keySet();
        for (Integer integer : integers) {
            System.out.println(integer + ":" + map.get(integer));
        }
        System.out.println("***************");
        for (Map.Entry<Integer, String> next : map.entrySet()) {
            System.out.println(next.getKey() + ":" + next.getValue());
        }
        System.out.println("***************");
        for (String v : map.values()) {
            System.out.println(v);
        }
    }
}
